package main.Q601_700;

import java.util.*;

public class Q681_690 {
    public static void main(String[] args) {
        System.out.println("Question681：");
        System.out.println("Question682：棒球比赛");
        System.out.println("Question683：");
        System.out.println("Question684：冗余连接");
        System.out.println("Question685：");
        System.out.println("Question686：");
        System.out.println("Question687：");
        System.out.println("Question688：");
        System.out.println("Question689：");
        System.out.println("Question690：员工的重要性");
    }
}

class Question682 {
    public int calPoints(String[] operations) {
        List<Integer> scores = new ArrayList<>();
        int result = 0;
        for (String op : operations) {
            if (op.equals("C")) {
                scores.remove(scores.get(scores.size() - 1));
            } else if (op.equals("D")) {
                Integer lastScore = scores.get(scores.size() - 1);
                scores.add(lastScore * 2);
            } else if (op.equals("+")) {
                Integer lastScore = scores.get(scores.size() - 1);
                Integer preScore = scores.get(scores.size() - 2);
                scores.add(lastScore + preScore);
            } else {
                scores.add(Integer.valueOf(op));
            }
        }
        for (Integer score : scores) {
            result += score;
        }
        return result;
    }
}

class Question684 {
    int[] parents;

    public int process1(int node) {//寻找顶层元素
        while (parents[node] != node) {
            node = parents[node];
        }
        return node;
    }

    public void process2(int node1, int node2) {//合并量集合
        parents[process1(node1)] = process1(node2);
    }

    public int[] findRedundantConnection(int[][] edges) {
        int length = edges.length;
        parents = new int[length + 1];
        for (int i = 1; i <= length; i++) parents[i] = i;
        for (int i = 0; i < length; i++) {
            int node1 = edges[i][0], node2 = edges[i][1];
            if (process1(node1) != process1(node2)) {
                process2(node1, node2);
            } else return edges[i];
        }
        return null;
    }
}

class Employee {
    public int id;
    public int importance;
    public List<Integer> subordinates;
}

class Question690 {
    public int getImportance(List<Employee> employees, int id) {
        Map<Integer, Employee> map = new HashMap<>();
        for (Employee employee : employees) {
            map.put(employee.id, employee);
        }
        int result = map.get(id).importance;
        Queue<Integer> queue = new LinkedList<>();
        queue.addAll(map.get(id).subordinates);
        while (!queue.isEmpty()) {
            Integer cur = queue.poll();
            queue.addAll(map.get(cur).subordinates);
            result += map.get(cur).importance;
        }
        return result;
    }
}